Communication between electronic devices is drawing more attention as the speeds of such electronic devices are increasing. One type of electronic communications architecture for interconnecting electronic devices is the RAPIDIO standard, described in “The RapidIO™ Interconnect Specification,” Revision 1.2, June, 2002, published by the RapidIO Trade Association. The RapidIO architecture is configured for interconnecting microprocessors, digital signal processors (DSPs), communications and network processors, system memory, peripheral devices, and the like on a circuit board or several circuit boards using a backplane. The RapidIO architecture provides for packet-switched point-to-point technology for passing data and control information within embedded systems, primarily used in network and communications equipment.
In a RAPIDIO system, two ports are interconnected via a link. Each port has a transmitter and a receiver connected to the other port's receiver and transmitter, respectively. The pair of ports implements flow control to prevent the loss of packets due to a lack of buffer space in a receiver. The flow control mechanism does not use any external arbitration or sideband signaling, but is rather completely in-band.
The RAPIDIO standard implements two flow control mechanisms: a receiver-controlled mechanism and a transmitter-controlled mechanism. In the transmitter-controlled mechanism, physical layer (PHY) logic in a transmitter receives a buffer status packet from a receiver, which indicates the number of packets the receiver can buffer. The PHY logic uses that information to anticipate how many packets the receiver can receive and transmit only that many packets. In addition to anticipating how many packets should be sent, the transmitter-controlled mechanism prioritizes packets that are scheduled to be sent such that the packets are not necessarily sent in the order they were produced.
Notably, each of the packets includes a header having a priority field. The field is normally produced by layers higher than the PHY logic in a transmitter. As the buffers in the receiver are depleted, the transmitter becomes more selective and will utilize the priorities to determine which packet is sent. Priorities range from zero to three, where zero is the lowest priority. In addition, the RAPIDIO standard defines two types of packets: request packets and response packets. Response packets are never assigned the lowest priority, and request packets are never assigned the highest priority. A response packet's priority field may be incremented (“promoted”) by the transmitter if necessary to fill the receiver's buffer.
The RAPIDIO standard details several algorithms to implement transmitter-controlled flow control. FIG. 1 is a flow diagram depicting an exemplary algorithm 100 for implementing transmitter-controlled flow control. In the algorithm 100, the transmitter PHY logic includes multiple buffers, each buffer storing a packet. Together, the buffers provide a queue of packets. The algorithm 100 begins at step 101. At step 102, a determination is made as to whether a packet is available in the queue to be sent. If not, the algorithm 100 returns to step 101. If so, at step 104, a determination is made as to whether the transmitter port is using a receiver-controlled flow control mechanism. If so, the next packet in the queue is sent at step 106. Otherwise, at step 108, a determination is made as to whether the next packet in the queue meets a minimum priority. The minimum priority corresponds to a worst-case estimate of the number of free buffers left in the receiver.
If the next packet in the queue meets the minimum priority, that packet is sent at step 110. Otherwise, at step 112, a determination is made as to whether any packet in the queue meets the minimum priority. If so, the oldest packet that meets the minimum priority is placed at the head of the queue at step 114. At step 116, the next packet in the queue is sent (i.e., the oldest packet that meets the minimum priority). If no packet in the queue meets the minimum priority, at step 118, a determination is made as to whether any packet in the queue is a response packet. If so, the oldest response packet is placed at the head of the queue at step 120. At step 122, the oldest response packet is promoted to have the minimum priority. At step 124, the next packet in the queue is sent (i.e., the oldest response packet). If there are no response packets in the queue, the algorithm 100 returns to step 101.
Implementation of the algorithm 100 shown in FIG. 1 at high speeds is difficult. Since the packets may not be transmitted in sequence (due to re-prioritization), “gaps” will be created, where some buffers in the transmitter are empty, but surrounding buffers are still pending. Since packet data is constantly being buffered, there is no bandwidth to “recompact” the buffers. One conventional implementation of the algorithm 100 is to sequentially inspect the packets to determine which packet to transmit using a processor or state machine that checks the packets one-by-one. However, in some high-speed applications, there is no time to sequentially inspect all queued packets to find the next packet to send without inducing a stall. Accordingly, there exists a need in the art for an improved packet re-shuffler and a method of implementing the same.